package com.ljy.my_study.leetcode.文本左右对齐;

import java.util.ArrayList;
import java.util.List;

/**
 * @author lijunying
 * @date 2021/9/9 11:33
 */
public class TestMain {

//    给定一个单词数组和一个长度 maxWidth，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。
//
//    你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。
//
//    要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
//
//    文本的最后一行应为左对齐，且单词之间不插入额外的空格。
//
//    说明:
//
//    单词是指由非空格字符组成的字符序列。
//    每个单词的长度大于 0，小于等于 maxWidth。
//    输入单词数组 words 至少包含一个单词。
//    示例:
//
//    输入:
//    words = ["This", "is", "an", "example", "of", "text", "justification."]
//    maxWidth = 16
//    输出:
//            [
//               "This    is    an",
//               "example  of text",
//               "justification.  "
//            ]
//    示例 2:
//
//    输入:
//    words = ["What","must","be","acknowledgment","shall","be"]
//    maxWidth = 16
//    输出:
//            [
//              "What   must   be",
//              "acknowledgment  ",
//              "shall be        "
//            ]
//    解释: 注意最后一行的格式应为 "shall be    " 而不是 "shall     be",
//                 因为最后一行应为左对齐，而不是左右两端对齐。
//    第二行同样为左对齐，这是因为这行只包含一个单词。
//    示例 3:
//
//    输入:
//    words = ["Science","is","what","we","understand","well","enough","to","explain",
//                     "to","a","computer.","Art","is","everything","else","we","do"]
//    maxWidth = 20
//    输出:
//            [
//              "Science  is  what we",
//            "understand      well",
//              "enough to explain to",
//              "a  computer.  Art is",
//              "everything  else  we",
//              "do                  "
//            ]
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/text-justification
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    public static void main(String[] args) {
        System.out.println(new TestMain().fullJustify(new String[]{"ab","111"},
                3));
//        System.out.println(new TestMain().fullJustify(new String[]{"What","must","be","acknowledgment","shall","be"},
//                16));
//        System.out.println(new TestMain().fullJustify(new String[]{"Science","is","what","we","understand","well",
//                "enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"},20));
    }

    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> result=new ArrayList<>();
        int width=0;
        List<String> list=new ArrayList<>();
        for(String w:words){
            int newWidth=width+w.length();
            if(list.size()!=0){
                newWidth+=list.size();
            }
            if(newWidth>maxWidth){
                result.add(merge(list,width,maxWidth,true));
                list.clear();
                width=0;
            }
            list.add(w);
            width+=w.length();
        }
        if(!list.isEmpty()){
            result.add(merge(list,width,maxWidth,false));
        }
        return result;
    }

    private String merge(List<String> list,int width,int maxWidth,boolean fullJustify){
        int size=list.size();
        int num=size-1==0?1:size-1;
        int count=(maxWidth-width)/num;
        int more=(maxWidth-width)%num;
        if(!fullJustify&&size!=1){
            count=1;
            more=0;
        }
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<size;i++){
            sb.append(list.get(i));
            if(i!=size-1||size==1){
                for(int j=0;j<count;j++){
                    sb.append(" ");
                }
                if(i<more){
                    sb.append(" ");
                }
            }
        }
        int len=sb.length();
        for(int i=len;i<maxWidth;i++){
            sb.append(" ");
        }
        return sb.toString();
    }
}
